package org.bear.linkList;

import java.util.HashMap;
import java.util.Map;

public class LRUCache2 {

    private static class Node{
        int key;
        int value;
        Node pre;
        Node next;

        public Node(int key, int value){
            this.key = key;
            this.value = value;
        }
    }

    int sizeLimit = 0;
    Node head = new Node(-1, -1);
    Node tail = head;
    Map<Integer, Node> nodeMap;

    public LRUCache2(int capacity) {
        nodeMap = new HashMap<>(capacity);
        sizeLimit = capacity;
    }

//    p 0 1 2
    public int get(int key) {
        Node node = nodeMap.get(key);
        if(node == null){
            return -1;
        }
        // 移动key节点到链表尾
        moveNodeToTail(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node = nodeMap.get(key);
        if(node == null){
            if (nodeMap.size() == sizeLimit) {
                // 1. 移动首个节点到链表尾, 再将首个节点的值修改 2. nodeMap删除首个节点的key， 在插入首个节点
                Node neededNode = head.next;
                nodeMap.remove(neededNode.key);
                neededNode.key = key;
                neededNode.value = value;
                moveNodeToTail(neededNode);
                nodeMap.put(key, neededNode);
            }else{
                // 链表尾插入新节点 2. nodeMap插入新节点
                Node newNode = new Node(key, value);
                nodeMap.put(key, newNode);
                tail.next = newNode;
                newNode.pre = tail;
                tail = tail.next;
            }
        }else{
            // 移动key节点到链表尾， key节点值修改  2. nodeMap不动
            moveNodeToTail(node);
            node.value = value;
        }
    }


    private void moveNodeToTail(Node node){
        if (tail == node) {
            return;
        }
        node.pre.next = node.next;
        node.next.pre = node.pre;
        tail.next = node;
        node.pre = tail;
        node.next = null;
        tail = tail.next;
    }
}
